package leetcode.code1434;

import java.util.List;

// 帽子给人，决定每一个帽子给什么人
public class Solution2 {

	List<List<Integer>> hats;
	int n;
	int mod = (int) 1e9 + 7;
	int limit;

	public int numberWays(List<List<Integer>> hats) {
		this.n = hats.size();
		this.hats = hats;
		this.limit = (1 << n) - 1;
		Integer[][] dp = new Integer[41][1 << n];
		return f(1, 0, dp);
	}

	private int f(int hat, int state, Integer[][] dp) {
		if (state == limit) {
			return 1;
		}
		if (hat == 41) {
			return 0;
		}
		if (dp[hat][state] != null) {
			return dp[hat][state];
		}
		long ans = f(hat + 1, state, dp);
		for (int i = 0; i < n; i++) {
			if (((state >> i) & 1) == 0) {
				List<Integer> list = hats.get(i);
				if (list.contains(hat)) {
					ans += f(hat + 1, state | (1 << i), dp);
					ans %= mod;
				}
			}
		}
		dp[hat][state] = (int) ans;
		return (int) ans;
	}
}
